package dataStructureAlgorithms;

import java.util.*;

/**
 * @Description: TODO 排序算法 升序
 * @Author: wzj
 * @Date: 2019/10/10 8:05
 */
public class Sort0 {

    // TODO 交换排序
    /**
     * TODO 冒泡排序
     * 1、a[i]比a[i+1]大，就交换，反之不动
     * 2、比较a[i+1]和a[i+2],操作同1
     * @param arr
     */
    public static void bubbleSort(int[] arr){
        int len=arr.length,temp;
        for(int i=0;i<len-1;i++){ //排几次
            System.out.println("第 "+(i+1)+" 次排序");
            for(int j=0;j<len-1-i;j++){ //
                if(arr[j]>arr[j+1]){
                    temp=arr[j+1];
                    arr[j+1]=arr[j];
                    arr[j]=temp;
                }
                System.out.println(Arrays.toString(arr));
            }
        }
    }

    /**
     * TODO 快速排序
     * 通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，分别对这两部分记录继续进行排序，以达到整个序列有序。
     * 1、从左边找比基准数大的，从右边找比基准数小的，通常选择第一个为基准数，先从右往左找比基准数小的数
     * 2、从右往左找，找到比基准数小的数a，记录a的位置aindex，替换基准数位置值为a，从左向右找
     * 3、从左向右找，找到比基准数大的数b，记录b的位置bindex，替换aindex位置值为b，从aindex往左找
     * 4、重复2 3
     * @param arr
     */
    public static void quickSort(int[] arr,int startIndex,int endIndex){
        int low=startIndex,high=endIndex;
        if(low<high){
            int pivot=arr[low];//基准值
            while (low<high){
                //右侧的数大于或等于基准值时，不用管，继续向左移动下标high，直到找到比基准数小的数或者high等于low时结束下标high的移动
                while(arr[high]>=pivot && high>low){
                    high--;
                }
                arr[low]=arr[high];
                //左侧的数小于或等于基准值时，不用管，继续向左移动下标low，直到找到比基准数大的数或者high等于low时结束下标low的移动
                while(arr[low]<=pivot && low<high){
                    low++;
                }
                arr[high]=arr[low];
            }
            arr[low]=pivot;//此时low=high，下标重合，赋基准值
            quickSort(arr,startIndex,low-1);
            quickSort(arr,low+1,endIndex);
        }
    }

    //TODO 插入排序

    /**
     * TODO 简单插入排序
     * 从下标为1的数开始，和它前面的所有数进行对比
     * @param arr
     */
    public static void insertSort(int[] arr){
        int temp;
        for(int i=1;i<arr.length;i++){
            int j=i;
            // 用while而不用for(int j=i;j>0;j--)是因为可以减少循环次数，没必要一直判断到arr[0]，因为当前数之前的数都是有序的，只要找到比当前数小的数的位置就可以停止
            while(j>=1 && arr[j]<arr[j-1]){
                temp=arr[j-1];
                arr[j-1]=arr[j];
                arr[j]=temp;
                j--;
            }
        }
    }

    /**
     * TODO 希尔(缩小增量)排序
     * @param arr
     */
    public static void shellSort(int[] arr){
        int temp;
        for(int d=arr.length/2;d>0;d/=2){
            //下面操作同简单插入排序，只不过增加了for(int d=arr.length/2;d>0;d/=2)这一层增量循环
            for(int i=d;i<arr.length;i++){
                int j=i;
                while(j>=d && arr[j]<arr[j-d]){
                    temp=arr[j];
                    arr[j]=arr[j-d];
                    arr[j-d]=temp;
                    j-=d;
                }
            }
        }
    }

    //TODO 选择排序

    /**
     * TODO 简单选择
     * @param arr
     */
    public static void selectSort(int[] arr){
        int index,temp;
        for(int i=0;i<arr.length-1;i++){
            index=i;
            for(int j=i;j<arr.length;j++){
                if(arr[j]<arr[index]){
                    index=j;
                }
            }
            if(index!=i){
                temp=arr[i];
                arr[i]=arr[index];
                arr[index]=temp;
            }
        }
    }

    /**
     * TODO 堆排序
     * @param arr
     */
    public static void heapSort(int[] arr){
        // 将数组调整为大顶堆，应该从最后一个非叶子节点开始调整，节点n的左子节点为2n+1，右为2n+2，
        // 完全二叉树一定有左子节点，所以最后一个非叶子节点用(arr.length-1)/2计算求出

        //先把数组构建成大顶堆
        int index=(arr.length-1)/2;//最后一个非叶子节点
        for(int i=index;i>=0;i--){
            bigHeap(arr,i,arr.length);
        }
        //在大顶堆的基础上，交换构建的堆的首尾数据，然后重新构建大顶堆，交换首尾...
        for(int i=arr.length-1;i>=0;i--){
            int temp=arr[0];
            arr[0]=arr[i];
            arr[i]=temp;
            bigHeap(arr,0,i);//要构建堆的数组长度每次-1
        }
    }

    /**
     * 构建大顶堆 使用的是数组
     * @param arr 构建大顶堆的数组
     * @param index 要构建的父节点
     * @param size 要构建用到的数的个数
     */
    public static void bigHeap(int[] arr,int index,int size){
        int leftNodeIndex=2*index+1,rightNodeIndex=2*index+2,temp;
        if(leftNodeIndex<size && arr[leftNodeIndex]>arr[index]){
            temp=arr[leftNodeIndex];
            arr[leftNodeIndex]=arr[index];
            arr[index]=temp;
            bigHeap(arr,leftNodeIndex,size);
        }
        if(rightNodeIndex<size && arr[rightNodeIndex]>arr[index]){
            temp=arr[rightNodeIndex];
            arr[rightNodeIndex]=arr[index];
            arr[index]=temp;
            bigHeap(arr,rightNodeIndex,size);
        }
    }

    //TODO 基数排序
    /**
     * TODO 基数排序-数组
     * 从低(个)位向高位排序
     * @param arr
     */
    public static void radixArraySort(int[] arr){
        //确定要排序的次数，为最大值的位数
        int maxNum=arr[0];
        for(int i=1;i<arr.length;i++){
            if(arr[i]>maxNum){
                maxNum=arr[i];
            }
        }
        int sortCount=(maxNum+"").length();//排序次数
        int[][] radix=new int[10][arr.length];//0-9每个位置对应一个数组
        int[] index=new int[10];//记录0-9每个位置数组的下标
        for(int i=0,n=1;i<sortCount;i++,n*=10){//n用作除数
            //存
            for(int j=0;j<arr.length;j++){
                int ys=arr[j]/n%10; //余数
                radix[ys][index[ys]]=arr[j];
                index[ys]=index[ys]+1;
            }
            //取
            int m=0;
            for(int j=0;j<radix.length;j++){
                for(int k=0;k<index[j];k++){
                    arr[m]=radix[j][k];
                    m++;
                }
                index[j]=0;//重置每个位置的下标为0
            } //取的时候并没有重置radix数组，因为是根据index获取数据，没必要重置数组
        }
    }
    /**
     * TODO 基数排序-队列
     * @param arr
     */
    public static void radixQueueSort(int[] arr){
        int maxNum=arr[0];
        for(int i=1;i<arr.length;i++){
            if(arr[i]>maxNum){
                maxNum=arr[i];
            }
        }
        int sortCount=(maxNum+"").length();
        ArrayQueue[] queue=new ArrayQueue[10];
        for(int i=0;i<queue.length;i++){
            queue[i]=new ArrayQueue();
        }
        for(int i=0,n=1;i<sortCount;i++,n*=10){
            for(int j=0;j<arr.length;j++){
                int ys=arr[j]/n%10;
                queue[ys].add(arr[j]);
            }
            int m=0;
            for(int j=0;j<queue.length;j++){
                while(!queue[j].isEmpty()){
                    arr[m]=queue[j].poll();
                    m++;
                }
            }
        }
    }
    /**
     * TODO 基数排序-List
     * 和使用队列差不多
     * @param arr
     */
    public static void radixListSort(int[] arr){
        int maxNum=arr[0];
        for(int i=1;i<arr.length;i++){
            if(arr[i]>maxNum){
                maxNum=arr[i];
            }
        }
        int sortCount=(maxNum+"").length();
        List<Integer>[] list=new ArrayList[10];
        for(int i=0;i<10;i++){
            list[i]=new ArrayList<>();
        }
        for(int i=0,n=1;i<sortCount;i++,n*=10){
            for(int j=0;j<arr.length;j++){
                int ys=arr[j]/n%10;
                list[ys].add(arr[j]);
            }
            int m=0;
            for(int j=0;j<list.length;j++){
                while(!list[j].isEmpty()){
                    while(list[j].size()>0){
                        arr[m]=list[j].get(0);
                        m++;
                        list[j].remove(0);
                    }
                }
            }
        }
    }

    //TODO 归并排序

    /**
     * 拆分-合并
     * @param arr
     * @param low
     * @param high
     */
    public static void mergeSort(int[] arr,int low,int high){
        if(low<high){
            int middle=(low+high)/2;
            mergeSort(arr,low,middle);
            mergeSort(arr,middle+1,high);
            merge(arr,low,high);
        }
    }

    /**
     * 合并，数
     * @param arr
     * @param low
     * @param high
     */
    public static void merge(int[] arr,int low,int high){
        int middle=(low+high)/2;
        int i=low,j=middle+1,k=0;
        int[] arrTemp=new int[high-low+1];
        while(i<=middle && j<=high){
            if(arr[i]>arr[j]){
                arrTemp[k]=arr[j];
                j++;
            } else {
                arrTemp[k]=arr[i];
                i++;
            }
            k++;
        }
        while(i<=middle){
            arrTemp[k]=arr[i];
            k++;
            i++;
        }
        while(j<=high){
            arrTemp[k]=arr[j];
            k++;
            j++;
        }
        for(int m=0;m<arrTemp.length;m++){
            arr[low+m]=arrTemp[m];
        }
//        System.out.println(Arrays.toString(arr));
    }
    public static void main(String[] args) {
        int[] arr={7,6,5,4,2,1,4};
//        System.out.println("数组长度："+arr.length);
        heapSort(arr);
//        mergeSort(new int[]{1},new int[]{2});
        System.out.println(Arrays.toString(arr));
    }
}
